// LinkedList.cpp : Defines the entry point for the console application.
//

#include "stdio.h"


struct elementType
{	
	int	data;
	struct elementType *next;
};

struct elementType *head = NULL;
struct elementType *tail = NULL;


int Delete(elementType *elem)
{
	struct elementType *currPos;
	
	//Check for empty list
	if(head == NULL)
		return 0;

	

	//Are we deleting head ?
	if(elem == head){
		head = head->next;
		delete elem;

		//Is it a single element list ?
		if(head == NULL)
			tail = NULL;			

		return 1;
	}

	
	//Find previous element to elem, head is not checked as its checked be4
	currPos = head;
	while(currPos->next != NULL){
		//Delete element
		if(currPos->next == elem){
			currPos->next = elem->next;
			delete elem;

			//Was tail deleted?
			if(currPos->next == NULL)
				tail = currPos;

			return 1;
		}		
		currPos = currPos->next;
	}
	

	//Not found
	return 0;
}




int InsertAfter(elementType *elem, int data)
{
	//We need to assign memory in all cases, so do it rightaway
	elementType *newPos;
	newPos = new elementType();

	if(newPos == NULL)
		return 0;

	newPos->data = data;
		
	//Are we inserting at head ?
	if(elem == NULL){
		newPos->next = elem;
		head = newPos;

		//Was list empty be4 ?, then tail also needs updating
		if(tail == NULL)
			tail = newPos;
		return 1;
	}
	
	newPos->next = elem->next;
	elem->next = newPos;
	
	//Insertion was after tail, update tail
	if(newPos->next == NULL)
		tail = newPos;

	return 1;
	

}


void RemoveHead(elementType **head1)
{
	if(head1 && *head1){
		elementType *temp = (*head1)->next; /* Line 2 */
		delete (*head1) ; /* Line 1 */
		*head1 = temp;
	}
}

int GetMth2Last(elementType **ppelem, int m)
{
	int i = 0;
	elementType *m_behind = head, *curPos = head;

	if(head == NULL)
		return 0;

	while(curPos){			

		//start dragging m_behind only after diff betw curPos & m_behind > m, else no need(whether i at least m, is chked below)
		if(i > m)
			m_behind = m_behind->next;

		curPos = curPos->next;
		i++;
	}

	//i never reached m, return error, reduce i to get the i with which m was chked
	if((i-1) < m){
		ppelem = NULL;
		return 0;
	}

	*ppelem = m_behind;
	return 1;
}

int main(int argc, char* argv[])
{
	int i;
	elementType *pelem;

	for(i=1; i<=10; i++)
		if(InsertAfter(head, i))
			printf("Inserted %d \n", i);

	//Print list
	for(elementType *p = head; p != NULL; p = p->next)
				printf("%d\n", p->data);


	for(i=0; i<12; i++)
		if(GetMth2Last(&pelem, i))
			printf("%dth to last element is %d \n", i, pelem->data);
		
	

/*	while(Delete(head)){
			printf("Deleted !\n");
			for(elementType *p = head; p != NULL; p = p->next)
				printf("%d\n", p->data);
	}*/

	
	return 0;
}

